package Hard;

// 最大矩形
/*
 * 没思路，看答案
 *
 * */
public class Solution85 {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;
        int x = matrix.length;
        int y = matrix[0].length;
        int max = Integer.MIN_VALUE;
        int leftMatrix[][] = new int[x][y];
        for (int i = 0; i < x; i++) {
            int count = 0;
            for (int j = 0; j < y; j++) {
                if (matrix[i][j] == '1') {
                    count++;
                    leftMatrix[i][j] = count;
                } else {
                    count = 0;
                    leftMatrix[i][j] = 0;
                }
            }
        }
//        int dp[][] = new int[x][y];
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                // a*b，b=height，a=min（leftMatrix[k][j]） ,  0 <= k <= i
                int a = Integer.MAX_VALUE, b = 0;
                for (int k = i; k >= 0; k--) {
                    a = Math.min(leftMatrix[k][j], a);
                    b++;
                    if (a * b > max) max = a * b;
                }

            }
        }
        return max;
    }
}
